package com.jack.leetcode.array;

public class 在排序数组中查找元素的第一个和最后一个位置 {

    public int[] searchRange(int[] nums, int target) {
        if (nums == null) {
            return new int[]{-1, -1};
        }
        int n = nums.length;
        int i = binarySearch(nums, 0, n - 1, target);
        if (i == -1) {
            return new int[]{-1, -1};
        } else {
            int left = i - 1, right = i + 1;

            while (left >= 0 && nums[left] == target) {
                left--;
            }
            while (right < n && nums[right] == target) {
                right++;
            }
            return new int[]{left + 1, right - 1};
        }
    }

    public int binarySearch(int[] nums, int i, int j, int target) {
        if (i > j) {
            return -1;
        }
        int mid = (i + j) / 2;
        if (target == nums[mid]) {
            return mid;
        } else if (target > nums[mid]) {
            return binarySearch(nums, mid + 1, j, target);
        } else {
            return binarySearch(nums, i, mid - 1, target);
        }
    }
}
